
 let g: number[][] = []
 // 下面三个变量，对应列、行、3x3区块是否已经有某个数字，
 // 如c[1][9]代表下标为1的那一列是否有9
 let c: boolean[][] = []
 let r: boolean[][] = []
 let b: boolean[][][] = []
 let ok = false
 
 function f(x: number) {
   return Math.floor(x)
 }
 
 function init(board: string[][]) {
   // 内存开大点因为一会儿会使用列下标+行下标表示所在斜线
   for (let i = 0; i < 30; i++) {
     // c[i] = r[i] = rc[i] = cr[i] = [] // 不可以使用连等号，这样所有数组会指向同一个对象
     c[i] = []
     r[i] = []
 
     for (let j = 0; j <= 9; j++) {
       c[i][j] = r[i][j] = false
     }
   }
   for (let i = 0; i < 3; i++) {
     b[i] = []
     for (let j = 0; j < 3; j++) {
       b[i][j] = []
       for (let k = 0; k <= 9; k++) {
         b[i][j][k] = false
       }
     }
   }
   for (let i = 0; i < board.length; i++) {
     g[i] = []
     for (let j = 0; j < board[i].length; j++) {
       if (board[i][j] == ".") {
         g[i][j] = 0
       } else {
         g[i][j] = parseInt(board[i][j])
         if(r[i][g[i][j]] || c[j][g[i][j]] || b[f(i / 3)][f(j / 3)][g[i][j]]){
           console.log('无解')
         }
         r[i][g[i][j]] = c[j][g[i][j]] = true
         b[f(i / 3)][f(j / 3)][g[i][j]] = true
       }
     }
   }
 }
 
 function dfs(x: number, y: number, board: string[][]) {
   if (ok) {
     return
   }
   if (x == 9) {
     ok = true;
     for (let i = 0; i < 9; i++) {
       for (let j = 0; j < 9; j++) {
         board[i][j] = g[i][j] ? g[i][j].toString() : '.'
       }
     }
     return
   }
   if (g[x][y] != 0) {
     if (y == 8) {
       dfs(x + 1, 0, board);
     } else {
       dfs(x, y + 1, board);
     }
   } else {
 
     for (let j = 1; j <= 9; j++) {
       if (!r[x][j] && !c[y][j] && !b[f(x / 3)][f(y / 3)][j]) {
         r[x][j] = c[y][j] = b[f(x / 3)][f(y / 3)][j] = true
         g[x][y] = j;
         if (y == 8) {
           dfs(x + 1, 0, board);
         } else {
           dfs(x, y + 1, board);
         }
         r[x][j] = c[y][j] = b[f(x / 3)][f(y / 3)][j] = false
         g[x][y] = 0;
       }
     }
   }
 
 }
 
 export function solveSudoku(board: string[][]): void {
   init(board)
   dfs(0, 0, board)
   console.log(board)
 };
 
/*  solveSudoku([
   ["3", "9", "9", "7", "4", "8", ".", ".", "."],
   ["7", ".", ".", ".", ".", ".", ".", ".", "."],
   [".", "2", ".", "1", ".", "9", ".", ".", "."],
   [".", ".", "7", ".", ".", ".", "2", "4", "."],
   [".", "6", "4", ".", "1", ".", "5", "9", "."],
   [".", "9", "8", ".", ".", ".", "3", ".", "."],
   [".", ".", ".", "8", ".", "3", ".", "2", "."],
   [".", ".", ".", ".", ".", ".", ".", ".", "6"],
   [".", ".", ".", "2", "7", "5", "9", ".", "."]
 ]) */